package uestc.lj.basic.tree;

import java.util.Stack;

/**
 * 递归和非递归的前中后序遍历二叉树
 *
 * @Author:Crazlee
 * @Date:2021/11/23
 */
public class Code01_PreinPosTraversal {
	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	/**
	 * 递归前序
	 *
	 * @param head 二叉树头结点
	 */
	public static void preOrderRecur(Node head) {
		if (head == null) {
			return;
		}
		System.out.println(head.value + " ");
		preOrderRecur(head.left);
		preOrderRecur(head.right);
	}

	/**
	 * 非递归前序遍历二叉树
	 *
	 * @param head 二叉树头结点
	 */
	public static void preOrderUnRecur(Node head) {
		System.out.print("非递归前序遍历二叉树：");
		if (head == null) {
			return;
		}
		Stack<Node> stack = new Stack<>();
		stack.push(head);
		while (!stack.isEmpty()) {
			head = stack.pop();
			System.out.print(head.value + " ");
			if (head.right != null) {
				stack.add(head.right);
			}
			if (head.left != null) {
				stack.add(head.left);
			}
		}
		System.out.println();
	}

	/**
	 * 递归中序
	 *
	 * @param head 二叉树头结点
	 */
	public static void inOrderRecur(Node head) {
		if (head == null) {
			return;
		}
		inOrderRecur(head.left);
		System.out.println(head.value + " ");
		inOrderRecur(head.right);
	}

	/**
	 * 非递归实现二叉树中序遍历
	 *
	 * @param head 二叉树头结点
	 */
	public static void inOrdedrUnRecur(Node head) {
		System.out.print("非递归中序遍历二叉树：");
		if (head == null) {
			return;
		}
		Stack<Node> stack = new Stack<>();
		while (!stack.isEmpty() || head != null) {
			if (head != null) {
				stack.push(head);
				head = head.left;
			} else {
				head = stack.pop();
				System.out.print(head.value + " ");
				head = head.right;
			}
		}
		System.out.println();
	}

	/**
	 * 递归后序
	 *
	 * @param head 二叉树头结点
	 */
	public static void postOrderRecur(Node head) {
		if (head == null) {
			return;
		}
		postOrderRecur(head.left);
		postOrderRecur(head.right);
		System.out.println(head.value + " ");
	}

	/**
	 * 使用辅助栈完成非递归后序遍历
	 *
	 * @param head 二叉树头结点
	 */
	public static void postOrderUnRecurByHelp(Node head) {
		System.out.print("辅助栈的非递归后序遍历：");
		if (head == null) {
			return;
		}
		Stack<Node> stack = new Stack<>();
		Stack<Node> help = new Stack<>();
		stack.push(head);
		while (!stack.isEmpty()) {
			head = stack.pop();
			help.push(head);
			if (head.left != null) {
				stack.push(head.left);
			}
			if (head.right != null) {
				stack.push(head.right);
			}
		}
		while (!help.isEmpty()) {
			System.out.print(help.pop().value + " ");
		}

		System.out.println();
	}

	/**
	 * 非递归实现后序遍历二叉树
	 *
	 * @param head 二叉树头结点
	 */
	public static void postOrderUnRecur(Node head) {
		if (head == null) {
			return;
		}
		System.out.print("非递归后序遍历二叉树顺序：");
		Stack<Node> stack = new Stack<>();
		stack.push(head);
		Node cur = null;
		while (!stack.isEmpty()) {
			cur = stack.peek();
			if (cur.left != null && head != cur.left && head != cur.right) {
				stack.push(cur.left);
			} else if (cur.right != null && head != cur.right) {
				stack.push(cur.right);
			} else {
				System.out.print(stack.pop().value + " ");
				head = cur;
			}
		}
		System.out.println();
	}
}
